1. Field of the Invention
The invention relates to concurrency control and, in particular, to lock management techniques that allow efficient bulk delegation of locks in database and/or transaction processing systems.
2. Description of the Related Art
Delegation of locks forms a basis for concurrency control in many modem transaction models, such as nested transaction models (see e.g., J. E. B. Moss, Nested Transactions: An Approach to Reliable Distributed Computing, Ph.D. thesis, Massachusetts Institute of Technology, Apr. 1981; T. Harder and K. Rothermel. Concurrency Control Issues in Nested Transactions, VLDB Journal, 2(1):39-74, 1993), split-join transaction models (see e.g., C. Pu, G. E. Kaiser, and N. Hutchinson, Split-Transactions for Open-Ended Activities, In Proc. of the ACM SIGMOD Int. Conf. on Management of Data, pp. 26-37, 1988; G. E. Kaiser and C. Pu, Dynamic Restructuring of Transactions, In Database Transaction Models for Advanced Applications, Data Management Systems, Morgan-Kaufman, pp. 266-295, 1992), colored actions (see e.g., S. K. Shrivastava and S. M. Wheater, Implementing Fault-Tolerant Distributed Applications Using Objects and Multi-coloured Actions, In Proc. of the Int. Conf. on Distributed Computing Systems, pp. 203-210, 1990), or the Apotram transaction model (see O. Anfindsen, Apotram—an Application-Oriented Transaction Model, Ph.D. thesis, University of Oslo, Department of Informatics, 1997). Various of these models are characterized by the delegation of locks at some point in the life of a transaction or assimilated entity. For example, the join operation of split-join transactions is a straightforward use of lock delegation. In the nested transaction model, a sub-transaction delegates all its locks to its parent transaction upon its commit. Similarly, lock delegation can be used to achieve the effect of moving objects upward or downward in a hierarchy of nested databases. Typically, a transaction model that imposes hierarchical structure and relies on locking for concurrency control uses some form of lock delegation to control lock ownership across levels of the hierarchy.
Often, transaction models assume that a transaction may delegate a single lock or a specific subset of its locks to other transactions. Often, it is desirable to delegate locks in bulk. For example, bulk delegation is assumed for most hierarchical transaction models, such as the nested transaction model, where delegation is useful to transfer the locks of a committed transaction to the next transaction up the hierarchy. Because commitment of a nested transaction is a common case, special attention should be paid to optimize bulk delegation. Unfortunately, most implementations focus on the case of single lock delegation and do not pay particular attention to efficiency of bulk delegation, instead implementing bulk delegation as a sequence of single lock delegation operations. Typically, such implementations of bulk delegation involve traversing and updating linked-lists of lock request control blocks (LRCBs). Scaling performance of such implementations is poor.
One alternative bulk delegation technique is the applicant's own prior work (described in L. Daynes, M. P. Atkinson, and P. Valduriez, Efficient Support for Customizing Concurrency Control in Persistent Java, In E. Bertino, S. Jajodia, and L. Kerschberg, editors, International Workshop on Advanced Transaction Models and Architectures (ATMA), pp. 216-233, Goa, India, Sep. 1996). Using that technique, the effect of a bulk lock delegation is achieved not by updating individual locks, but by changing the conflict detection mechanisms of the delegatee, using a lock manager ability's to represent ignore-conflict relationships between transactions. Unfortunately, while that technique tends to decouple the cost of bulk delegation from the number of locks delegated, it still suffers from poor scaling performance because space used to represent locks grows in proportion with the number of locks represented.
A bulk delegation implements a transfer of the ownership of a potentially large number of locks. The transfer is performed atomically with respect to all other locking operations, in particular, concurrent lock acquisition, release or delegation. In general, a validation of a bulk delegation verifies that the effect of a delegation of locks is legal, that is, that it results in lock values that can be otherwise achieved by a legal combination of lock release and acquisition for a given setting of ignore-conflict relationships (including when no ignore-conflict relationships are used).
A transaction model typically imposes and enforces some rules on how delegation and ignore-conflict relationships are used to implement its semantics. It is often the case that these rules guaranty that only valid requests for lock delegation are submitted to a lock manager. For instance, the locking and termination rules of a nested transaction model are such that validation is unnecessary in that case. However, in flexible transaction processing environment where applications are given access to the lock manager interface, in particular, for lock delegation and settings of ignore-conflict relationships, the lock manager cannot trust the applications to always submit valid lock delegation requests. Because the transfer of lock ownership needs to be atomic, a lock manager cannot discover that a bulk delegation is invalid while in the middle of processing it. Doing so may allow some transactions to see some effects of an invalid bulk delegation of locks and to wrongly exploit this error. It also raises the problem of undoing the bulk delegation of locks, which substantially adds complexity to a lock manager implementation. Instead, what is preferable is a fast validation method that can be employed prior to performing the bulk delegation to determine if the bulk delegation request is valid.
For such an approach to work, additional mechanisms are needed to ensure the atomicity of a bulk lock delegation. There are various ways that atomicity may be guaranteed. An obvious one is to block all locking operations during the processing of a bulk lock delegation, but this approach is in general unacceptable.
A minimum requirement to guarantee atomicity of a bulk delegation is to prevent the set of locks being delegated to change during the bulk delegation operation. A bulk delegation specifies the set of locks being delegated in an abstract way, e.g., the set of all the locks owned in write mode by a transaction. As a result, a concurrent lock acquisition by a delegator, or a concurrent delegation of locks to the delegator may change the set of locks being delegated. In order to prevent the set of delegated locks to change, the delegator must be prevented from performing other locking operations concurrently (e.g., release, delegate or acquire locks), or from being a delegatee in other concurrent lock delegation operations.
If ignore-conflict relationships between transactions are used, an additional requirement is to prevent the ignore-conflict relationships that involve any of the delegators and delegatees to change in a way that may impact the correctness of the bulk delegation (one can simply prevent removal of ignore-conflict relationships that involve any delegator or delegatee of the bulk delegation, as a fair conservative approximation of such changes).
In some cases, a transaction model may enforce the above requirements. For instance, implementations of the nested transaction model strictly limit the use of bulk delegation to when a sub-transaction terminates. In this case the sub-transaction is guaranteed not to perform any other locking operations since it is terminating. It is also guaranteed not to be involved in other lock delegation operations since only its own sub-transactions can delegate locks to it, and these must be already terminated in order for the first transaction to complete. Similarly, the use of ignore-conflict relationship by the nested transaction model is such that concurrent change to ignore-conflict relationships can never impact a bulk delegation.
To summarize, the atomicity of a bulk lock delegation can be achieved if:                the set of locks being delegated does not change during delegation,        ignore-conflict relationships involving the delegator transactions are not changed in ways that impact a lock delegation,        given the first two conditions, a validation method is used to guarantee that the bulk delegation will succeed.        
Irrespective of how the first two conditions are implemented, need exists for techniques that efficiently determine whether a bulk lock delegation is valid.